{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count the Number of Fair Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countFairPairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计公平数对的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始、长度为 <code>n</code> 的整数数组&nbsp;<code>nums</code>&nbsp;，和两个整数&nbsp;<code>lower</code> 和&nbsp;<code>upper</code> ，返回 <strong>公平数对的数目</strong> 。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>(i, j)</code>&nbsp;数对满足以下情况，则认为它是一个 <strong>公平数对</strong>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= i &lt; j &lt; n</code>，且</li>\n",
    "\t<li><code>lower &lt;= nums[i] + nums[j] &lt;= upper</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [0,1,7,4,4,5], lower = 3, upper = 6\n",
    "<b>输出：</b>6\n",
    "<b>解释：</b>共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。\n",
    "</pre>\n",
    "\n",
    "<p><b>示例 2：</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [1,7,9,2,5], lower = 11, upper = 11\n",
    "<b>输出：</b>1\n",
    "<b>解释：</b>只有单个公平数对：(2,3) 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>nums.length == n</code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>-10<sup>9</sup>&nbsp;&lt;= lower &lt;= upper &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-the-number-of-fair-pairs](https://leetcode.cn/problems/count-the-number-of-fair-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-the-number-of-fair-pairs](https://leetcode.cn/problems/count-the-number-of-fair-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,1,7,4,4,5]\\n3\\n6', '[1,7,9,2,5]\\n11\\n11']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self,nums,upper):\n",
    "        n = len(nums)\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        ans = 0\n",
    "        while l < r:\n",
    "            if nums[l]+nums[r] <= upper:\n",
    "                ans += r-l\n",
    "                l += 1\n",
    "            else:\n",
    "                r -= 1\n",
    "        return ans\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        return self.count(nums,upper)-self.count(nums,lower-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        counter_up = 0\n",
    "        counter_low = 0\n",
    "        nums.sort()\n",
    "        def counter(thre, nums):\n",
    "            left, right = 0, len(nums)-1\n",
    "            counter = 0\n",
    "            while left < right:\n",
    "                if nums[left] + nums[right] <= thre:\n",
    "                    counter += right - left\n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "            return counter\n",
    "        return counter(upper, nums) - counter(lower-1, nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 排序不会影响数对个数，因为求的是数对和，与里面的元素无关\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        def binary_search(nums, target, left, right):\n",
    "            # 返回第一个大于等于target的位置,可能范围：[0, right]\n",
    "            while left <= right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] < target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            return left\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            r = binary_search(nums, upper - nums[i] + 1, 0, i-1) # 限定右边界只是防止重复计数，不能取到右边界\n",
    "            l = binary_search(nums, lower - nums[i], 0, i-1)\n",
    "            ans += (r - l)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i, n in enumerate(nums):\n",
    "            ans += bisect_right(nums, upper - n, i + 1) - bisect_left(nums, lower - n, i + 1)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i , x in enumerate(nums):\n",
    "            l = bisect.bisect_left(nums,lower-x,0,i)\n",
    "            r = bisect.bisect_right(nums,upper-x,0,i)\n",
    "            res += r - l\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            r = bisect.bisect_right(nums, upper - x, 0, i)\n",
    "            l = bisect.bisect_left(nums, lower - x, 0, i)\n",
    "            ans += r - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        for i in range(len(nums)):\n",
    "            num1 = bisect.bisect_right(nums, upper - nums[i])\n",
    "            num2 = bisect.bisect_left(nums, lower - nums[i])\n",
    "            cnt += num1 - num2\n",
    "            if num2 <= i <= num1:\n",
    "                cnt -= 1\n",
    "        return cnt//2 + cnt%2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\r\n",
    "        # ans = 0\r\n",
    "        # for i in range(len(nums)-1):\r\n",
    "        #     l = lower - nums[i]\r\n",
    "        #     r = upper - nums[i]\r\n",
    "        #     temp = sorted(nums[i+1:])\r\n",
    "        #     ans += bisect_right(temp,r) - bisect_left(temp,l)\r\n",
    "        # return ans\r\n",
    "        ans = 0\r\n",
    "        nums.sort()\r\n",
    "        for j, x in enumerate(nums):\r\n",
    "            r = bisect_right(nums, upper - x, 0, j)\r\n",
    "            l = bisect_left(nums, lower - x, 0, j)\r\n",
    "            ans += r - l\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, i)\n",
    "            l = bisect_left(nums, lower - x, 0, i)\n",
    "            ans += r - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 数组中公平数对的数目：数对下标递增，数独数值之和在low,up之间\n",
    "        # 二分查找\n",
    "\n",
    "        # ans = 0\n",
    "        # nums.sort()\n",
    "        # for j, x in enumerate(nums):\n",
    "        #     r = bisect_right(nums, upper - x, 0, j)\n",
    "        #     l = bisect_left(nums, lower - x, 0, j)\n",
    "        #     ans += r - l\n",
    "        # return ans\n",
    "        \n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        N = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(1, N):\n",
    "            left = bisect_left(nums, lower-nums[i], 0, i)\n",
    "            right = bisect_right(nums, upper-nums[i],0,i)\n",
    "            ans += right - left\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        result=0\n",
    "\n",
    "        for i in range(len(nums)-1):\n",
    "            v1=nums[i]\n",
    "            vleft=lower-v1\n",
    "            vright=upper-v1\n",
    "            index1=bisect.bisect_left(nums,vleft)\n",
    "            index1=max(index1,i+1)\n",
    "            index2=bisect.bisect_right(nums,vright)\n",
    "            index2=max(index2,i+1)\n",
    "            num1=index2-index1\n",
    "            result+=max(0,num1)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        return sum(bisect_right(nums, upper-x, 0, i) - bisect_left(nums, lower-x, 0, i) for i, x in enumerate(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self, nums,upper):\n",
    "        n=len(nums)\n",
    "        l=0\n",
    "        r=n-1\n",
    "        c=0\n",
    "        while l<r:\n",
    "            if nums[l]+nums[r]<=upper:\n",
    "                c+=r-l\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return c\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        b=self.count(nums,upper)\n",
    "        a=self.count(nums,lower-1)\n",
    "        return b-a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        sol = 0\n",
    "\n",
    "        for i,num in enumerate(nums):\n",
    "            low = lower - num\n",
    "            up = upper - num\n",
    "            left_ind = bisect_left(nums,low,i+1)\n",
    "            right_ind = bisect_right(nums,up,i+1)\n",
    "            sol += right_ind - left_ind \n",
    "\n",
    "        return sol\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "#         ans = 0\n",
    "#         nums.sort()\n",
    "#         for j, x in enumerate(nums):\n",
    "#             r = bisect_right(nums, upper - x, 0, j)\n",
    "#             l = bisect_left(nums, lower - x, 0, j)\n",
    "#             ans += r - l\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for left,x in enumerate(nums):\n",
    "            l1 = bisect.bisect_left(nums,lower-x,lo=left+1)\n",
    "            l2 = bisect.bisect_right(nums,upper-x,lo = left+1)\n",
    "            ans +=l2-l1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for idx, x in enumerate(nums):\n",
    "            l = bisect.bisect_left(nums, lower - x, 0, idx)\n",
    "            r = bisect.bisect_right(nums,upper-x,0,idx)\n",
    "            res += r -l \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        m = len(nums)\n",
    "        res = 0\n",
    "        for i in range(m - 1):\n",
    "            target1 = lower - nums[i]\n",
    "            target2 = upper - nums[i]\n",
    "\n",
    "            left = i + 1\n",
    "            right = m - 1\n",
    "            while left < right:\n",
    "                middle = (left + right) // 2\n",
    "                if nums[middle] < target1:\n",
    "                    left = middle + 1\n",
    "                else:\n",
    "                    right = middle\n",
    "            if nums[left] < target1:\n",
    "                continue\n",
    "            x = left\n",
    "\n",
    "            left = i + 1\n",
    "            right = m - 1\n",
    "            while left < right:\n",
    "                middle = (left + right + 1) // 2\n",
    "                if nums[middle] <= target2:\n",
    "                    left = middle\n",
    "                else:\n",
    "                    right = middle - 1\n",
    "            if nums[left] > target2:\n",
    "                continue\n",
    "            y = left\n",
    "            res += (y - x + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int: \n",
    "        nums.sort()\n",
    "        c = 0\n",
    "        for i,v in enumerate(nums):\n",
    "            c += bisect_right(nums,upper-v,0,i) - bisect_left(nums,lower-v,0,i) \n",
    "        return c \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # 公平数对： 下标递增，数值和在low， up 之间\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for i, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, i)\n",
    "            l = bisect_left(nums, lower - x, 0, i)\n",
    "            ans += r - l \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        #bisect_left\n",
    "        #bisect_right \n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            right = bisect.bisect_right(nums,upper-nums[i],i+1,n)\n",
    "            left = bisect.bisect_left(nums,lower - nums[i],i+1,n)\n",
    "            ans += right - left\n",
    "            #print(i-lower,i-upper,left,right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = n-1,n-1\n",
    "        c = 0\n",
    "        # print(nums)\n",
    "        for i in range(n):\n",
    "            p,q = lower - nums[i], upper - nums[i]\n",
    "            while r >= 0 and nums[r] > q:\n",
    "                r -= 1\n",
    "            while l >= 0 and nums[l] >= p:\n",
    "                l -= 1\n",
    "            if r <= i:\n",
    "                continue\n",
    "            c += r-max(l,i)\n",
    "            # print(i,p,q,l,r,c)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def my_count(k):  # 统计 <= k 的数对数目，原问题等价于 <=upper 的数对数目减去 <=lower - 1 的数对数目\n",
    "            res = 0\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                t = nums[left] + nums[right]\n",
    "                if t <= k:  # 达到统计条件\n",
    "                    res += right - left  \n",
    "                  # 如果 nums[left] + nums[right] <= k, 那么下标从left + 1到right的数 + nums[left]都是 <= k 的\n",
    "                    left += 1\n",
    "                  # 继续统计 nums[left + 1] + nums[i] <= k 的数对\n",
    "                else: # right指针左移，使t减小\n",
    "                    right -= 1\n",
    "            return res\n",
    "\n",
    "        return my_count(upper) - my_count(lower - 1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for j, num in enumerate(nums):\n",
    "            left = bisect.bisect_left(nums, lower - num, 0, j)\n",
    "            right = bisect.bisect_right(nums, upper - num, 0, j)\n",
    "            ans += right - left\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        count = 0\n",
    "        # for i in range(len(nums)):\n",
    "        #     for j in range(i+1, len(nums)):\n",
    "        #         if (nums[i] + nums[j]) <= upper and lower <= (nums[i] + nums[j]):\n",
    "        #             count+=1\n",
    "\n",
    "        nums.sort()\n",
    "\n",
    "        n = len(nums)\n",
    "        p1, p2 = 0, n-1\n",
    "        while p1<p2:\n",
    "            if nums[p1] + nums[p2] > upper:\n",
    "                p2-=1\n",
    "            else:\n",
    "                count+=p2-p1\n",
    "                p1+=1\n",
    "        p1,p2 = 0,n-1\n",
    "\n",
    "        while p1 <p2:\n",
    "            if nums[p1] +nums[p2]<lower:\n",
    "                count -=p2-p1\n",
    "                p1+=1\n",
    "            else:\n",
    "                p2-=1\n",
    "\n",
    "\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        #解题思路：\n",
    "        #可对数组进行排序，假设j>i\n",
    "        #lower <= nums[i] + nums[j] <= upper \n",
    "        # --> lower-nums[i] <= nums[j] <= upper-nums[i]\n",
    "        # --> nums[m] <= nums[j] <= nums[n]\n",
    "        # --> m <= j <= n\n",
    "\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            l = bisect_left(nums,lower - nums[i],i + 1,n)\n",
    "            r = bisect_right(nums,upper - nums[i],i + 1,n)\n",
    "            res += r - l  # [l, r)内的所有元素都可以与nums[i]组成数对\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        result = 0\n",
    "        nums.sort()\n",
    "        for i in range(1,len(nums)):\n",
    "            left, right = 0, i-1\n",
    "            target = lower - nums[i]\n",
    "            while(left <= right):\n",
    "                mid = (left + right)//2\n",
    "                if(nums[mid] >= target):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            l = left\n",
    "            left, right = 0, i-1\n",
    "            target = upper - nums[i]\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums[mid] <= target):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            r = right \n",
    "            result  += r - l + 1\n",
    "        return result\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        #直接用二分法\n",
    "        #我来试着写一下\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "\n",
    "        print(nums)\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            # print(x)\n",
    "            # print(upper-x,nums[r],r)\n",
    "            # print(lower-x,nums[l],l)\n",
    "            ans += r - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        def lower_bound(ls, x, l, r):\n",
    "            left, right = l, r\n",
    "            while left+1<right:\n",
    "                mid = (left+right)//2\n",
    "                if ls[mid]>=x:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            return right\n",
    "        for i, x in enumerate(nums):\n",
    "            lower_idx = lower_bound(nums, lower-nums[i], i, len(nums))\n",
    "            upper_idx = lower_bound(nums, upper-nums[i]+1, i, len(nums))- 1\n",
    "            ans += upper_idx - lower_idx + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        #[0,1,4,4,5,7]\n",
    "        #range:[lower-nums[j],upper-nums[j]]\n",
    "        ans=0\n",
    "        for i,x in enumerate(nums):\n",
    "            l=bisect_left(nums,lower-x,0,i)\n",
    "            r=bisect_right(nums,upper-x,0,i)\n",
    "            ans += r-l\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        s = 0\n",
    "        for i in range(n-1):\n",
    "            left = bisect_left(range(i+1, n), lower, key=lambda x:nums[i]+nums[x])\n",
    "            right = bisect_right(range(i+1, n), upper, key=lambda x:nums[i]+nums[x])\n",
    "            s += right - left \n",
    "        return s \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            l, r = j+1, len(nums)-1\n",
    "            while l<=r:\n",
    "                m = l+(r-l)//2\n",
    "                if nums[m]>=lower-x:\n",
    "                    r = m-1\n",
    "                else:\n",
    "                    l = m+1\n",
    "\n",
    "            ll, rr = j+1, len(nums)-1\n",
    "            while ll<=rr:\n",
    "                m = ll+(rr-ll)//2\n",
    "                if nums[m]>upper-x:\n",
    "                    rr = m-1\n",
    "                else:\n",
    "                    ll = m+1\n",
    "\n",
    "            ans += rr-l+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        def lower_bound(ls, x, l, r):\n",
    "            left, right = l, r\n",
    "            while left+1<right:\n",
    "                mid = (left+right)//2\n",
    "                if ls[mid]>=x:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            return right\n",
    "        for i, x in enumerate(nums):\n",
    "            lower_idx = lower_bound(nums, lower-nums[i], i, len(nums))\n",
    "            upper_idx = lower_bound(nums, upper-nums[i]+1, i, len(nums))- 1\n",
    "            ans += upper_idx - lower_idx + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def my_count(k):  # 统计 <= k 的数对数目，原问题等价于 <=upper 的数对数目减去 <=lower - 1 的数对数目\n",
    "            res = 0\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                t = nums[left] + nums[right]\n",
    "                if t <= k:  # 达到统计条件\n",
    "                    res += right - left  \n",
    "                  # 如果 nums[left] + nums[right] <= k, 那么下标从left + 1到right的数 + nums[left]都是 <= k 的\n",
    "                    left += 1\n",
    "                  # 继续统计 nums[left + 1] + nums[i] <= k 的数对\n",
    "                else: # right指针左移，使t减小\n",
    "                    right -= 1\n",
    "            return res\n",
    "\n",
    "        return my_count(upper) - my_count(lower - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j,x in enumerate(nums):\n",
    "            r = bisect_right(nums,upper-x,0,j)\n",
    "            l = bisect_left(nums,lower-x,0,j)\n",
    "            ans+=r-l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans=0\n",
    "        nums.sort()\n",
    "        for j,x in enumerate(nums):\n",
    "            r=bisect_right(nums,upper-x,0,j)\n",
    "            l=bisect_left(nums,lower-x,0,j)\n",
    "            ans+=r-l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j) \n",
    "            ans += r - l  \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for j,x in enumerate(nums):\n",
    "            mn_i = lower - x\n",
    "            mx_i = upper - x\n",
    "            ans += max(0, bisect_right(nums, mx_i,0,j) - bisect_left(nums, mn_i,0,j))\n",
    "            # print(x, mn_i, mx_i, st)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        #bisect_left\n",
    "        #bisect_right \n",
    "        #公式代入错误\n",
    "        #错把i当成nums[i]\n",
    "        #范围指定错误i+1到n，而不是i到n\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            right = bisect.bisect_right(nums,upper-nums[i],i+1,n)\n",
    "            left = bisect.bisect_left(nums,lower - nums[i],i+1,n)\n",
    "            ans += right - left\n",
    "            #print(i-lower,i-upper,left,right)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l    \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 排序：不影响数目\n",
    "# 原问题等价于<=upper的数对数目减去<=lower - 1的数对数目\n",
    "# left向右移动，统计每次nums[left] + nums[i] <= k的数目，总和即为res\n",
    "# right移至 nums[left] + nums[right] <= k 处，那么下标从left + 1到right的数 + nums[left]都是 <= k 的\n",
    "# 易知left向右移后，满足条件的right需要左移或不动\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def my_count(k):  # 统计 <= k 的数对数目，原问题等价于 <=upper 的数对数目减去 <=lower - 1 的数对数目\n",
    "            res = 0\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                t = nums[left] + nums[right]\n",
    "                if t <= k:  # 达到统计条件\n",
    "                    res += right - left  \n",
    "                  # 如果 nums[left] + nums[right] <= k, 那么下标从left + 1到right的数 + nums[left]都是 <= k 的\n",
    "                    left += 1\n",
    "                  # 继续统计 nums[left + 1] + nums[i] <= k 的数对\n",
    "                else: # right指针左移，使t减小\n",
    "                    right -= 1\n",
    "            return res\n",
    "\n",
    "        return my_count(upper) - my_count(lower - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def counter(k):\n",
    "            res = 0\n",
    "            l,r = 0,n-1\n",
    "            while l<r:\n",
    "                s = nums[l] + nums[r]\n",
    "                if s <= k:\n",
    "                    res += r-l\n",
    "                    l += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "            return res\n",
    "        return counter(upper) - counter(lower-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        result = 0\n",
    "        nums.sort()\n",
    "        for i in range(1,len(nums)):\n",
    "            right = i - 1\n",
    "            left, right = 0, i-1\n",
    "            while(left <= right):\n",
    "                mid = (left + right)//2\n",
    "                if(nums[mid] >= lower - nums[i]):\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            l = left\n",
    "            left, right = 0, i-1\n",
    "            while(left <= right):\n",
    "                mid = (left+right)//2\n",
    "                if(nums[mid] <= upper - nums[i]):\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            r = right\n",
    "            result  += r - l + 1\n",
    "        return result\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def my_count(k):  # 统计 <= k 的数对数目，原问题等价于 <=upper 的数对数目减去 <=lower - 1 的数对数目\n",
    "            res = 0\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                t = nums[left] + nums[right]\n",
    "                if t <= k:  # 达到统计条件\n",
    "                    res += right - left  \n",
    "                  # 如果 nums[left] + nums[right] <= k, 那么下标从left + 1到right的数 + nums[left]都是 <= k 的\n",
    "                    left += 1\n",
    "                  # 继续统计 nums[left + 1] + nums[i] <= k 的数对\n",
    "                else: # right指针左移，使t减小\n",
    "                    right -= 1\n",
    "            return res\n",
    "\n",
    "        return my_count(upper) - my_count(lower - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        res = 0\n",
    "        nums.sort()\n",
    "        for i in range(len(nums)):\n",
    "            l = bisect_left(nums,lower - nums[i], i + 1, len(nums))\n",
    "            r = bisect_right(nums,upper - nums[i], i + 1, len(nums))\n",
    "            res += r - l\n",
    "        return res\n",
    "        \"\"\"\n",
    "        res = 0\n",
    "        for i in range(len(nums) - 1):\n",
    "            for j in range(i + 1,len(nums)):\n",
    "                if lower <= nums[i] + nums[j] and nums[i] + nums[j] <= upper: res += 1\n",
    "        return res超时\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        r = N = len(nums)\n",
    "        res = 0\n",
    "        l = bisect_left(nums, lower - nums[-1])\n",
    "        for l, n1 in enumerate(nums[l:N-1], l):\n",
    "            if n1 + nums[l+1] > upper: break\n",
    "            r = bisect_right(nums, upper - n1, l+1, r)\n",
    "            l = bisect_left(nums, lower - n1, l+1, r)\n",
    "            res += r - l\n",
    "        return res\n",
    "        # lower <= ni + nj <= upper\n",
    "        # lower - ni <= nj <= upper - ni\n",
    "\n",
    "\n",
    "        # ni >= lower - nums[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def findLessThan(nums,val):\n",
    "        l=0;r=len(nums)-1\n",
    "        ret=0\n",
    "        while l<r:\n",
    "            sums=nums[l]+nums[r]\n",
    "            if nums[l]+nums[r]<=val:\n",
    "                ret+=(r-l)\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ret\n",
    "class Solution:\n",
    "    def findLessThan(nums,val):\n",
    "        l=0;r=len(nums)-1\n",
    "        ret=0\n",
    "        while l<r:\n",
    "            sums=nums[l]+nums[r]\n",
    "            if nums[l]+nums[r]<=val:\n",
    "                ret+=(r-l)\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ret\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums=sorted(nums)\n",
    "        a=findLessThan(nums,upper)\n",
    "        b=findLessThan(nums,lower-1)\n",
    "        return a-b\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        #print(nums)\n",
    "        for i,ele in enumerate(nums):\n",
    "            r = bisect_right(nums,upper-ele,i+1,n)\n",
    "            l = bisect_left(nums,lower-ele,i+1,n)\n",
    "            res += max((r-l),0)\n",
    "            #print(l,r,res,upper-ele,lower-ele)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        lo = hi = len(nums) - 1\n",
    "        ans = 0\n",
    "\n",
    "        for i, v in enumerate(nums):\n",
    "            l = bisect_left(nums, lower - v, 0, i)\n",
    "            r = bisect_right(nums, upper - v, 0, i)\n",
    "            ans += r - l\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            right = bisect_right(nums, upper-x, 0, i)\n",
    "            left = bisect_left(nums, lower-x, 0, i)\n",
    "            ans += right - left\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self,nums,value):\n",
    "        n = len(nums)\n",
    "        ans=0\n",
    "        l = 0\n",
    "        r = n-1\n",
    "        while l<r:\n",
    "            if nums[l]+nums[r]<=value:\n",
    "                ans+=r-l\n",
    "                l+=1\n",
    "            else:\n",
    "                r-=1\n",
    "        return ans\n",
    "\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        a = self.count(nums,upper)\n",
    "        b = self.count(nums,lower-1)\n",
    "        return a-b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # nums 排序 lower-nums[j]<=nums[i]<=upper-nums[j]\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        def lower_bound(ls, x, l, r):\n",
    "            left, right = l, r\n",
    "            while left+1<right:\n",
    "                mid = (left+right)//2\n",
    "                if ls[mid]>=x:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid\n",
    "            return right\n",
    "        for i in range(n):\n",
    "            ans += (lower_bound(nums, upper-nums[i] + 1, i, n) - lower_bound(nums, lower-nums[i], i, n))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        def count(bound):\n",
    "            result, arr = 0, []\n",
    "            for i, x in enumerate(nums):\n",
    "                result += i - bisect_left(arr, x)\n",
    "                insort(arr, bound-x)\n",
    "            return result\n",
    "        return count(upper) - count(lower-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for i, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, i)\n",
    "            l = bisect_left(nums, lower - x, 0, i)\n",
    "            ans += r - l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n = len(nums)\n",
    "        nums.sort()\n",
    "\n",
    "        def my_count(k): # 统计 <= k 的数对数目\n",
    "            res = 0\n",
    "            left, right = 0, n - 1\n",
    "            while left < right:\n",
    "                t = nums[left] + nums[right]\n",
    "                if t <= k:\n",
    "                    res += right - left  \n",
    "                    left += 1\n",
    "                else:\n",
    "                    right -= 1\n",
    "            return res\n",
    "\n",
    "        return my_count(upper) - my_count(lower - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "#         ans = 0\n",
    "#         nums.sort()\n",
    "#         for j, x in enumerate(nums):\n",
    "#             r = bisect_right(nums, upper - x, 0, j)\n",
    "#             l = bisect_left(nums, lower - x, 0, j)\n",
    "#             ans += r - l\n",
    "#         return ans\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for left,x in enumerate(nums):\n",
    "            l1 = bisect.bisect_left(nums,lower-x,lo=left+1)\n",
    "            l2 = bisect.bisect_right(nums,upper-x,lo = left+1)\n",
    "            ans +=l2-l1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        for j in range(len(nums)):\n",
    "            number = nums[j]\n",
    "            # 不等式左侧\n",
    "            left = bisect_left(nums,lower-number,0,j)\n",
    "            # 不等式右侧\n",
    "            right = bisect_right(nums,upper-number,0,j)\n",
    "            ans += right - left \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        for j, x in enumerate(nums):\n",
    "            r = bisect_right(nums, upper - x, 0, j)\n",
    "            l = bisect_left(nums, lower - x, 0, j)\n",
    "            ans += r - l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            r = bisect_right(nums,upper-x,i+1,n) # upper_bound\n",
    "            l = bisect_left(nums,lower-x,i+1,n) # lower_bound\n",
    "            ans += r-l\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        ans = 0\n",
    "        a = nums\n",
    "        a.sort()\n",
    "        n = len(nums)\n",
    "        for i , v in enumerate(nums):\n",
    "            if i == len(nums):\n",
    "                break\n",
    "            #arr = a[i+1:]\n",
    "            # if not arr:\n",
    "            #     break\n",
    "            # if v + arr[0]>upper or v + arr[-1] < lower:\n",
    "            #     continue\n",
    "            l = bisect_left(a,lower-v,i+1,n)\n",
    "            if l == n:\n",
    "                continue\n",
    "            r = bisect_right(a,upper-v,i+1,n)\n",
    "            if not r:\n",
    "                continue\n",
    "            ans += r-l\n",
    "        return ans\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        cnt = 0\n",
    "        for j, val in enumerate(nums):\n",
    "            right = bisect_right(nums, upper-val,0,j)\n",
    "            left = bisect_left(nums, lower-val,0,j)\n",
    "            cnt += right - left \n",
    "        return cnt\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        for i,x in enumerate(nums):\n",
    "            r = bisect_right(nums,upper-x,i+1,n) # upper_bound\n",
    "            l = bisect_left(nums,lower-x,i+1,n) # lower_bound\n",
    "            ans += r-l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        res = 0\n",
    "        for i,j in enumerate(nums):\n",
    "            if j*2>upper:\n",
    "                break\n",
    "            idx1 = bisect.bisect_left(nums, lower-j)\n",
    "            idx2 = bisect.bisect_right(nums, upper-j)\n",
    "            res += idx2-max(idx1, i+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        n=len(nums)\n",
    "        # count=0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i+1,n):\n",
    "        #         if lower<=nums[i] + nums[j] <= upper:\n",
    "        #             count+=1\n",
    "        # return count\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        from bisect import bisect_left,bisect_right\n",
    "        for i in range(n):\n",
    "            r = bisect_right(nums, upper - nums[i], 0, i)\n",
    "            l=bisect_left(nums,lower-nums[i],0,i)\n",
    "            ans+=r-l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        #  lower-nums[j] <=  nums[i] <= upper-nums[j]\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            r = bisect_right(nums,upper-nums[j],0,j)\n",
    "            l = bisect_left(nums,lower-nums[j],0,j)\n",
    "            ans += r-l\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        # lower-nums[j]  <= nums[i] <= upper-nums[j]\n",
    "        # 枚举j,然后看符合情况的nums[i]有多少\n",
    "        # nums[i]的个数为 <= upper-nums[j]的个数 - < lower-nums[j]的个数\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            r = bisect_right(nums,upper-nums[j],0,j)# 从index开始都是大于x的\n",
    "            l = bisect_left(nums,lower-nums[j],0,j) # 从index开始都是大于等于x的\n",
    "            ans += r-l\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        res = 0\n",
    "        for x in nums:\n",
    "            res += sl.bisect_right(upper-x)-sl.bisect_left(lower-x)\n",
    "            sl.add(x)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ret = 0\n",
    "        tmp = []\n",
    "        for i in range(n):\n",
    "            l = lower - nums[i]\n",
    "            r = upper - nums[i]\n",
    "            pl = bisect_left(tmp, l)\n",
    "            pr = bisect_right(tmp, r)\n",
    "            # print(l, r, nums[i], nums[:i], pl, pr)\n",
    "            ret += pr - pl\n",
    "            tmp.append(nums[i])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: [int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        nn=len(nums)\n",
    "        dp=[]\n",
    "        tot=0\n",
    "        for p in range(nn):\n",
    "            rr=bisect.bisect_right(dp,upper-nums[p])\n",
    "            ll=bisect.bisect_left(dp,lower-nums[p])\n",
    "            tot+=rr-ll\n",
    "            dp.append(nums[p])\n",
    "\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l,r = n-1,n-1\n",
    "        c = 0\n",
    "        print(nums)\n",
    "        for i in range(n):\n",
    "            p,q = lower - nums[i], upper - nums[i]\n",
    "            while r >= 0 and nums[r] > q:\n",
    "                r -= 1\n",
    "            while l >= 0 and nums[l] >= p:\n",
    "                l -= 1\n",
    "            if r <= i:\n",
    "                continue\n",
    "            c += r-max(l,i)\n",
    "            print(i,p,q,l,r,c)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        l = ans = 0\n",
    "        while l < n:\n",
    "            x = nums[l]\n",
    "            up_index = bisect_right(nums, upper-x, l + 1, n)\n",
    "            lo_index = bisect_left(nums, lower-x, l + 1, n)\n",
    "            print(str(up_index)+\" hell\")\n",
    "            print(lo_index)\n",
    "            ans += up_index - lo_index\n",
    "            l += 1\n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
